package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class 二叉树的垂序遍历_987 {
            PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
                    if(a[0] != b[0]) return a[0] - b[0]; // a的值大于b，返回>0 就是升序 返回<0就是降序
                    if(a[1] != b[1]) return a[1] - b[1];
                    return a[2] - b[2];
            });
            public List<List<Integer>> verticalTraversal(TreeNode root) {
                dfs(root, 0, 0);
                List<List<Integer>> res = new ArrayList<>();
                while(!queue.isEmpty()) {
                     List<Integer> colList = new ArrayList<>();
                     int col = queue.peek()[0];
                     while(!queue.isEmpty() && queue.peek()[0] == col) {
                         colList.add(queue.poll()[2]);
                     }
                    res.add(colList);
                }
                return res;
            }

           // ** dfs标准递归写法  为  if(node == null ) return ; dfs(node.left) ; dfs(node.right) 但是此题需要保存左右节点的val  需要添加parameter
            private void dfs(TreeNode node, int col, int row){
                if(node == null) return;
                // 非空就保存本节点的值并递归  递归过程传递下一节点的col和row
                int[] tuple = new int[]{col, row, node.val};
                queue.offer(tuple);
                dfs(node.left, col -1, row + 1);
                dfs(node.right,col + 1, row + 1);
            }
        }